Weakly Monotonic Propagators
Identifieur interne : 000B55 ( Main/Exploration ); précédent : 000B54; suivant : 000B56Weakly Monotonic Propagators
Auteurs : Christian Schulte [Suède] ; Guido Tack [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2009.
Abstract
Abstract: Today’s models for propagation-based constraint solvers require propagators as implementations of constraints to be at least contracting and monotonic. These models do not comply with reality: today’s constraint programming systems actually use non-monotonic propagators. This paper introduces the first realistic model of constraint propagation by assuming a propagator to be weakly monotonic (complying with the constraint it implements). Weak monotonicity is shown to be the minimal property that guarantees constraint propagation to be sound and complete. The important insight is that weak monotonicity makes propagation in combination with search well behaved. A case study suggests that non-monotonicity can be seen as an opportunity for more efficient propagation.
Url:
DOI: 10.1007/978-3-642-04244-7_56
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000578
- to stream Istex, to step Curation: 000452
- to stream Istex, to step Checkpoint: 000625
- to stream Main, to step Merge: 000B64
- to stream Main, to step Curation: 000B55
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Weakly Monotonic Propagators</title><author><name sortKey="Schulte, Christian" sort="Schulte, Christian" uniqKey="Schulte C" first="Christian" last="Schulte">Christian Schulte</name></author><author><name sortKey="Tack, Guido" sort="Tack, Guido" uniqKey="Tack G" first="Guido" last="Tack">Guido Tack</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:A339EB8A1FD4EE983F91C904D8EE4D13B6C8BB36</idno><date when="2009" year="2009">2009</date><idno type="doi">10.1007/978-3-642-04244-7_56</idno><idno type="url">https://api.istex.fr/document/A339EB8A1FD4EE983F91C904D8EE4D13B6C8BB36/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000578</idno><idno type="wicri:Area/Istex/Curation">000452</idno><idno type="wicri:Area/Istex/Checkpoint">000625</idno><idno type="wicri:doubleKey">0302-9743:2009:Schulte C:weakly:monotonic:propagators</idno><idno type="wicri:Area/Main/Merge">000B64</idno><idno type="wicri:Area/Main/Curation">000B55</idno><idno type="wicri:Area/Main/Exploration">000B55</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Weakly Monotonic Propagators</title><author><name sortKey="Schulte, Christian" sort="Schulte, Christian" uniqKey="Schulte C" first="Christian" last="Schulte">Christian Schulte</name><affiliation wicri:level="1"><country xml:lang="fr">Suède</country><wicri:regionArea>KTH - Royal Institute of Technology</wicri:regionArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Suède</country></affiliation></author><author><name sortKey="Tack, Guido" sort="Tack, Guido" uniqKey="Tack G" first="Guido" last="Tack">Guido Tack</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Programming Systems Lab, Saarland University</wicri:regionArea><wicri:noRegion>Saarland University</wicri:noRegion><wicri:noRegion>Saarland University</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2009</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno></series><idno type="istex">A339EB8A1FD4EE983F91C904D8EE4D13B6C8BB36</idno><idno type="DOI">10.1007/978-3-642-04244-7_56</idno><idno type="ChapterID">Chap56</idno><idno type="ChapterID">56</idno></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Today’s models for propagation-based constraint solvers require propagators as implementations of constraints to be at least contracting and monotonic. These models do not comply with reality: today’s constraint programming systems actually use non-monotonic propagators. This paper introduces the first realistic model of constraint propagation by assuming a propagator to be weakly monotonic (complying with the constraint it implements). Weak monotonicity is shown to be the minimal property that guarantees constraint propagation to be sound and complete. The important insight is that weak monotonicity makes propagation in combination with search well behaved. A case study suggests that non-monotonicity can be seen as an opportunity for more efficient propagation.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>Suède</li></country></list><tree><country name="Suède"><noRegion><name sortKey="Schulte, Christian" sort="Schulte, Christian" uniqKey="Schulte C" first="Christian" last="Schulte">Christian Schulte</name></noRegion><name sortKey="Schulte, Christian" sort="Schulte, Christian" uniqKey="Schulte C" first="Christian" last="Schulte">Christian Schulte</name></country><country name="Allemagne"><noRegion><name sortKey="Tack, Guido" sort="Tack, Guido" uniqKey="Tack G" first="Guido" last="Tack">Guido Tack</name></noRegion><name sortKey="Tack, Guido" sort="Tack, Guido" uniqKey="Tack G" first="Guido" last="Tack">Guido Tack</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Musique/explor/MozartV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000B55 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000B55 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Musique
|area= MozartV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:A339EB8A1FD4EE983F91C904D8EE4D13B6C8BB36
|texte= Weakly Monotonic Propagators
}}
| This area was generated with Dilib version V0.6.20. |  |